package com.c2b.algorithm.leetcode.base;

import java.util.HashMap;
import java.util.Map;

/**
 * <a href='https://leetcode.cn/problems/copy-list-with-random-pointer/'>随机链表的复制(Copy List with Random Pointer)</a>
 * <p>给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。</p>
 * <p>构造这个链表的<a color='blue'>深拷贝</a>。 深拷贝应该正好由n个 全新节点组成，其中每个新节点的值都设为其对应的原节点的值。
 * 新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。
 * 复制链表中的指针都不应指向原链表中的节点 。</p>
 * <p>例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。</p>
 * <p>返回复制链表的头节点。</p>
 * <p>用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：
 * <ul>
 * <li>val：一个表示 Node.val 的整数。</li>
 * <li>random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为  null 。</li>
 * </ul>
 * 你的代码只接受原链表的头节点 head 作为传入参数。</p>
 * <p>
 *     <b>示例</b>
 *      <pre>// 具体题目示例去原题中查看</pre>
 *      </p>
 * <p>
 *     <b>提示：</b>
 *     <ul>
 *          <li>0 <= n <= 1000</li>
 *          <li>-10^4 <= Node.val <= 10^4</li>
 *          <li>Node.random 为 null 或指向链表中的节点。</li>
 *     </ul>
 * </p>
 *
 * @author c2b
 * @see LC0002AddTwoNumbers_M 两数相加(Add Two Numbers)
 * @see LC0019RemoveNthNodeFromEndOfList_M 删除链表的倒数第 N 个结点(Remove Nth Node From End of List)
 * @see LC0021MergeTwoSortedLists_S 合并两个有序链表(Merge Two Sorted Lists)
 * @see LC0023MergeKSortedLists 合并 K 个升序链表(Merge k Sorted Lists)
 * @see LC0024SwapNodesInPairs_M 两两交换链表中的节点(Swap Nodes in Pairs)
 * @see LC0025ReverseNodesInKGroup_H K 个一组翻转链表(Reverse Nodes in k-Group)
 * @see LC0138CopyListWithRandomPointer_M 随机链表的复制(Copy List with Random Pointer)
 * @see LC0141LinkedListCycle_S 环形链表(Linked List Cycle)
 * @see LC0142LinkedListCycle_II_M 环形链表 II(Linked List Cycle II)
 * @see LC0146LRUCache_M LRU 缓存(LRU Cache)
 * @see LC0148SortList_M 排序链表(Sort List)
 * @see LC0160IntersectionOfTwoLinkedLists_S 相交链表(Intersection of Two Linked Lists)
 * @see LC0206ReverseLinkedList_S 反转链表(Reverse Linked List)
 * @see LC0234PalindromeLinkedList_S 回文链表(Palindrome Linked List)
 * @since 2023/4/27 17:01
 */
public class LC0138CopyListWithRandomPointer_M {
    static class Solution {

        /**
         * 用哈希表，记录源节点 和 对应的copyNode的映射关系
         */
        public Node copyRandomList(Node head) {
            if (head == null) {
                return null;
            }
            Map<Node, Node> copyMap = new HashMap<>();
            // 建立源节点与复制节点的映射关系
            Node currNode = head;
            while (currNode != null) {
                copyMap.put(currNode, new Node(currNode.val));
                currNode = currNode.next;
            }
            // 修改复制节点的next和random指针
            currNode = head;
            while (currNode != null) {
                copyMap.get(currNode).next = copyMap.get(currNode.next);
                copyMap.get(currNode).random = copyMap.get(currNode.random);
                currNode = currNode.next;
            }
            return copyMap.get(head);
        }

        public Node copyRandomList2(Node head) {
            if (head == null) {
                return null;
            }
            // 在原链表每个节点后面增加复制节点。例如：1->2->3->null ==> 1->1'->2->2'->3->3'->null
            Node curNode = head;
            while (curNode != null) {
                // 在当前节点 和 下一个节点中，增加一个copyNode
                Node copyNode = new Node(curNode.val);
                copyNode.next = curNode.next;
                curNode.next = copyNode;
                curNode = copyNode.next;
            }
            // 改变copyNode的random指针指向
            curNode = head;
            while (curNode != null) {
                curNode.next.random = curNode.random == null ? null : curNode.random.next;
                curNode = curNode.next.next;
            }
            // 改变copyNode的next指针指向。并且恢复原链表
            //Node ret = new Node(-1);
            //ret.next = head;
            //Node tempRet = ret;
            //curNode = head;
            //while (curNode != null) {
            //    // 记录copyNode
            //    Node copyNode = curNode.next;
            //    curNode.next = copyNode.next;
            //    tempRet.next = copyNode;
            //    curNode = curNode.next;
            //    tempRet = tempRet.next;
            //}
            //return ret.next;

            // 如果不需要恢复原来的链表
            curNode = head.next;
            while (curNode != null && curNode.next != null) {
                curNode.next = curNode.next.next;
                curNode = curNode.next;
            }
            return head.next;
        }
    }

    // Definition for a Node.
    static class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }


    public static void main(String[] args) {
        Node node7 = new Node(7);
        Node node13 = new Node(13);
        Node node11 = new Node(11);
        Node node10 = new Node(10);
        Node node1 = new Node(1);
        node7.next = node13;
        node7.random = null;
        node13.next = node11;
        node13.random = node7;
        node11.next = node10;
        node11.random = node1;
        node10.next = node1;
        node10.random = node11;
        node1.next = null;
        node1.random = node7;
        Solution solution = new Solution();
        Node node = node7;
        while (node != null) {
            System.out.print(node.val);
            if (node.next != null) {
                System.out.print(" -> ");
            } else {
                System.out.println();
            }
            node = node.next;
        }
        node = solution.copyRandomList2(node7);
        while (node != null) {
            System.out.print(node.val);
            if (node.next != null) {
                System.out.print(" -> ");
            } else {
                System.out.println();
            }
            node = node.next;
        }
    }
}